import java.util.HashMap;

/**
 * @program: LeetCode
 * @description: LeetCode :
 * @author: WXY
 * @create: 2022-12-27 10:48
 * @Version 1.0
 **/

public class offer_ten2_LRUCache {


     class LRUCache {



        public  class Node {
            public int key;
            public int value;
            public Node last;
            public Node next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }

        }

        // 双向链表
        // 从head到tail所有节点都是串好的
        public  class NodeDoubleLinkedList<K, V> {
            private Node head;
            private Node tail;

            public NodeDoubleLinkedList() {
                head = null;
                tail = null;
            }

            //如果有新节点加入就放入尾巴上；
            public void addNode(Node newNode) {
                if (newNode == null) return;
                if (head == null) {
                    head = newNode;
                    tail = newNode;
                } else {
                    tail.next = newNode;
                    newNode.last = tail;
                    tail = newNode;
                }
            }

            //移动一个node到尾巴上，潜台词，双向链表上有这个node
            //node f分离出，但是node前后环境重新连接
            //node放到尾巴上
            public void moveNodeToTail(Node node) {
                if (this.tail == node) {
                    return;
                }
                if (this.head == node) { // 当前node是老头部
                    this.head = node.next;
                    this.head.last = null;
                } else { // 当前node是中间的一个节点
                    node.last.next = node.next;
                    node.next.last = node.last;
                }
                node.last = this.tail;
                node.next = null;
                this.tail.next = node;
                this.tail = node;
            }

            //把头节点删掉并返回
            public Node removeHead() {
                if (this.head == null) {
                    return null;
                }
                Node res = this.head;
                if (this.head == this.tail) {
                    this.head = null;
                    this.tail = null;
                } else {
                    this.head = res.next;
                    res.next = null;
                    this.head.last = null;
                }
                return res;
            }
        }


        private HashMap<Integer, Node> keyNodeMap;
        private NodeDoubleLinkedList<Integer, Integer> nodeList;
        private final int capacity;

        public LRUCache(int capacity) {
            if (capacity < 1) {
                throw new RuntimeException("shoule be more than 0");
            }
            keyNodeMap = new HashMap<Integer, Node>();
            nodeList = new NodeDoubleLinkedList<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            if (keyNodeMap.containsKey(key)) {
                Node res = keyNodeMap.get(key);
                nodeList.moveNodeToTail(res);
                return res.value;
            }
            return -1

                    ;
        }

        public void put(int key, int value) {
            if (keyNodeMap.containsKey(key)) {
                Node node = keyNodeMap.get(key);
                node.value = value;
                nodeList.moveNodeToTail(node);
            } else {
                if (keyNodeMap.size() == capacity) {
                    removeMostUnuseCache();
                }
                Node newNode = new Node(key, value);
                keyNodeMap.put(key,newNode);
                nodeList.addNode(newNode);
            }
        }

        private void removeMostUnuseCache() {
            Node removeNode = nodeList.removeHead();
            keyNodeMap.remove(removeNode.key);
        }

    }
}
